// 两数之和

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class Solution{
public:

    vector<int> twoSum(vector<int> & nums, int target){
        // 这个复杂度比较高 O(n^2)，效果不好
        // vector<int> result;

        // for(int i=0; i < nums.size() - 1; i++){
            
        //     for(int j=i+1; j < nums.size(); j++){
        //         if (nums[i] + nums[j] == target){
        //             result.push_back(i);
        //             result.push_back(j);
        //         }
        //     }
        // }

        // return result;

        // 使用hash表解决
        unordered_map<int, int> hash; // 相当于是一个迭代器
        for(int i=0; i < nums.size(); i++){
            int complement = target - nums[i]; // 计算补数

            // hash.find()如果没有找到存储过的元素则会返回 hash.end()
            if (hash.find(complement) != hash.end()){

                return {hash[complement], i};
            }

            hash[nums[i]] = i;
        }

        return {};
        

    }

};

int Print(vector<int> a){
    for(int i=0; i < a.size(); i++){
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

int main(){
    vector<int> nums;
    nums = {1, 2, 3, 4, 5, 6};
    int target = 4;

    Solution solution;

    vector<int> result = solution.twoSum(nums, target);
    Print(result);

    return 0;
}

